#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<pair<int, int>> relation;
        int n = ratings.size();
        for (int i = 0; i < n; i++)
        {
            relation.push_back({ ratings[i], i });
        }
        sort(relation.begin(), relation.end());
        vector<int> count(n, 0);
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            int index = relation[i].second;
            int get = 0;
            if (index - 1 >= 0)
                get = max(get, ratings[index - 1] == ratings[index] ? 1 : count[index - 1] + 1);
            if (index + 1 < n)
                get = max(get, ratings[index + 1] == ratings[index] ? 1 : count[index + 1] + 1);
            count[index] = get;
            res += get;
        }
        return max(res, 1);
    }
};